package com.mamingchao.basic.arraysort.mergesort;

/**
 *  TimSort 是改进的 归并排序多路归并排序
 *  Tim sort --> java python 对象排序专用
 *  TimSort  有一个min_merge ，比如是16；原数组一次分多块（比如4块），每块如果长度大于min_merge
 *  就继续分。如果小于 min_merge，使用 banirysort(插入排序的一种，查找插入排序的位置是二叉搜索)
 *
 *
 *  自己实现的，代码有点丑陋
 * Created by mamingchao on 2021/3/10.
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] subArr1 = {1,3,5,7,9};
        int[] subArr2 = {2,4,6,8};
        int[] newArr = merge(subArr1,subArr2);
        for (int i = 0; i < newArr.length; i++) {
            System.out.print(newArr[i] + "\t");
        }
    }

    /**
     * 两个已然排好序的数组归并成一个排好顺的大数组
     * @param subArr1
     * @param subArr2
     * @return
     */
    private static int[] merge(int[] subArr1,int[] subArr2) {
        int[] newArr = new int[subArr1.length + subArr2.length];

        //子数组1 的索引
        int i = 0;
        //子数组2 的索引
        int j = 0;
        //新申请的大数组的索引
        int k = 0;

        while (i< subArr1.length && j<subArr2.length) {
            if (subArr1[i] < subArr2[j]) {
                newArr[k++] = subArr1[i++];

            } else if (subArr1[i] > subArr2[j]) {
                newArr[k++] = subArr2[j++];
            } else { // 如果 i 位置的值和 j位置的值，相同的话
                newArr[k++] = subArr1[i++];
                newArr[k++] = subArr2[j++];
            }
        }

        //说明 subArr2 所有的element 都放到新数组里面去了
        if (i < subArr1.length) {
            appender(newArr,subArr1,i,k);
        }

        //说明 subArr1 所有的element 都放到新数组里面去了,subArr2的没全部放完，但剩下的都是大的，直接
        //把剩下的全部拿出来贴到新数组后面
        if (j < subArr2.length) {
            appender(newArr,subArr2,j,k);
        }

        return newArr;
    }



    private static void appender(int[] newArr,int[] oldArr,int oldIndex,int newIndex) {
        if (oldIndex < oldArr.length) {
            for (int l = oldIndex; l <oldArr.length; l++) {
                newArr[newIndex++] = oldArr[l];
            }
        }
    }

}


